#include "RKUtils.h"

/*******************************************************************
 * Some supporting functions for calculating Rabin Karp fingerprints
 *******************************************************************/

//HashValue_t modpower(HashValue_t base, HashValue_t exp, HashValue_t modulo) {
//  HashValue_t result = 1;
//  while(exp > 0) {
//    if(exp & 1 > 0)
//      result = (result * base) % modulo;
//    exp = exp >> 1;
//    
//    base = (base * base) % modulo;
//  }
//  return result;
//}

HashValue_t modpower(HashValue_t base_in, HashValue_t exp, HashValue_t modulo_in) {
  unsigned long long result = 1;
  unsigned long long base = base_in;
  unsigned long long modulo = modulo_in;
  while(exp > 0) {
    if(exp & 1 > 0)
      result = (result * base) % modulo;
    exp = exp >> 1;
    base = (base * base) % modulo;
//printf("base %llu, result %llu, modulo %llu", base, result, modulo);
//getc(stdin);
  }
  return result;
}

HashValue_t modabs(HashValue_t a, HashValue_t modulo)
{
  if(a >= 0)
    return a % modulo;
  else
    return (modulo - (-a) % modulo) % modulo;
}

HashValue_t modadd(HashValue_t a, HashValue_t b, HashValue_t modulo)
{
  return (a + b) % modulo;
}

HashValue_t modmult(HashValue_t a, HashValue_t b, HashValue_t modulo)
{
  return ((a % modulo) * (b % modulo)) % modulo;
}

HashValue_t modmult64(HashValue_t a, HashValue_t b, HashValue_t modulo)
{
    long long al=a;
//    long long bl=b;
//    return ((al % modulo) * (bl % modulo)) % modulo;
    return (al * b) % modulo;
}

HashValue_t modradpow64(long long radix, int radixPower, HashValue_t modulo)
{
    // returns X = (radix**radixPower) % modulo
    long long rl=radix;
    while (radixPower-- > 1)
        rl = (rl * radix) % modulo;
return rl;
}

HashValue_t modradmult64(long long a, HashValue_t radix, int radixPower, HashValue_t modulo)
{
    // returns X = (a * radix**radixPower) % modulo
    long long rl = modradpow64(radix, radixPower, modulo);
    return (a * rl) % modulo;
}

HashValue_t radmult(HashValue_t a, int radixPower, HashValue_t modulo)
{
    // returns X = (a * radix**radixPower) % modulo
    while (radixPower-- > 1)
        a = (a * 2) % modulo;
    return a;
}



HashValue_t hash_value(const char *text, int start, int end, HashValue_t radix, HashValue_t modulo)
{
  HashValue_t v = 0;
  for(int i=0; i < (end-start); i++)
    v = modadd(
          modmult64(radix, v, modulo),
          text[i+start] % radix,
          modulo);
  return v;
}

HashValue_t incr_hash_value(HashValue_t vold, int cold, int cnew, HashValue_t h, HashValue_t radix, HashValue_t modulo)
{
  HashValue_t v;
  // v = radix * (vold - cold * h) + cnew  mod modulo
  v = modadd(cnew % radix,
        modmult(radix, 
          modabs(vold-modmult(cold % radix, h, modulo), 
          modulo),
        modulo),
      modulo);
  return v;
}

